We consider a distributed system of n identical mobile robots operating in the two dimensional Euclidian plane. As in the previous studies, we consider the robots to be anonymous, oblivious, dis-oriented, and without any communication capabilities, operating based on the Look-Compute-Move model where the next location of a robot depends only on its view of the current configuration. Even in this seemingly weak model, most formation problems which require constructing specific configurations, can be solved quite easily when the robots are fully synchronized with each other. In this paper we introduce and study a new class of problems which, unlike the studied formation problems, cannot always be solved even in the fully synchronous model with atomic and rigid moves. This class of problems requires the robots to permute their locations in the plane. In particular, we are interested in implementing two special types of permutations - permutations without any fixed points and permutations of order n. The former (called Move-All) requires each robot to visit at least two of the initial locations, while the latter (called Visit-All) requires every robot to visit each of the initial locations in a periodic manner. We provide a characterization of the solvability of these problems, showing the main challenges in solving this class of problems for mobile robots. We also provide algorithms for the feasible cases, in particular distinguishing between one-step algorithms (where each configuration must be a permutation of the original configuration) and multi-step algorithms (which allow intermediate configurations). These results open a new research direction in mobile distributed robotics which has not been investigated before.

Oblivious permutations on the plane / Das, S.; Di Luna, G. A.; Flocchini, P.; Santoro, N.; Viglietta, G.; Yamashita, M.. - 153:(2020). (Intervento presentato al convegno International Conference on Principles of Distributed Systems tenutosi a Neuchatel; Switzerland) [10.4230/LIPIcs.OPODIS.2019.24].

Oblivious permutations on the plane

Di Luna G. A.
Secondo
;
2020

Abstract

We consider a distributed system of n identical mobile robots operating in the two dimensional Euclidian plane. As in the previous studies, we consider the robots to be anonymous, oblivious, dis-oriented, and without any communication capabilities, operating based on the Look-Compute-Move model where the next location of a robot depends only on its view of the current configuration. Even in this seemingly weak model, most formation problems which require constructing specific configurations, can be solved quite easily when the robots are fully synchronized with each other. In this paper we introduce and study a new class of problems which, unlike the studied formation problems, cannot always be solved even in the fully synchronous model with atomic and rigid moves. This class of problems requires the robots to permute their locations in the plane. In particular, we are interested in implementing two special types of permutations - permutations without any fixed points and permutations of order n. The former (called Move-All) requires each robot to visit at least two of the initial locations, while the latter (called Visit-All) requires every robot to visit each of the initial locations in a periodic manner. We provide a characterization of the solvability of these problems, showing the main challenges in solving this class of problems for mobile robots. We also provide algorithms for the feasible cases, in particular distinguishing between one-step algorithms (where each configuration must be a permutation of the original configuration) and multi-step algorithms (which allow intermediate configurations). These results open a new research direction in mobile distributed robotics which has not been investigated before.
2020
International Conference on Principles of Distributed Systems
and phrases distributed algorithms; chirality; fully synchronous; mobile robots; oblivious; permutations; sequence of configurations
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Oblivious permutations on the plane / Das, S.; Di Luna, G. A.; Flocchini, P.; Santoro, N.; Viglietta, G.; Yamashita, M.. - 153:(2020). (Intervento presentato al convegno International Conference on Principles of Distributed Systems tenutosi a Neuchatel; Switzerland) [10.4230/LIPIcs.OPODIS.2019.24].
File allegati a questo prodotto
File Dimensione Formato  
Das_Oblivious_2020.pdf

accesso aperto

Note: https://doi.org/10.4230/LIPIcs.OPODIS.2019.24
Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 2.56 MB
Formato Adobe PDF
2.56 MB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1421365
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact